package dataTypeTests;

import java.util.Collections;
import java.util.List;
import java.util.Random;

public class OneWayListTester<T extends Comparable<? super T>>  implements DataTypeTester<T> {
	List<T> list;
	
	OneWayListTester(List<T> list) {
		this.list = list;
	}
	
	@Override
	public long measureBinSearch(int iterations) {
		long avgTime = 0;
		Collections.sort(list);
		for (int i = 0; i < iterations; i++) {
			OneWayList<T> oneWayList = new OneWayList<T>(list);
			Random random = new Random();
			int index = random.nextInt(list.size()-1);
			T elem = oneWayList.getData(index);
			int listSize = list.size();
			long estTime = System.nanoTime();
			binSearch(oneWayList, elem, 0, listSize-1);
			estTime = System.nanoTime() - estTime;
			avgTime += estTime;
		}
		avgTime /= iterations;
		return avgTime;
	}
	
	private int binSearch(OneWayList<T> oneWayList, T elem, int l, int r) {
		if (l == r) {
			if (oneWayList.getData(l).compareTo(elem) == 0) return l;
		}
		int middle = (r + l) / 2;
		T middleData = oneWayList.getData(middle);
		int compare = middleData.compareTo(elem);
		if (compare == 0) return middle;
		if (compare < 0) return binSearch(oneWayList, elem, middle+1, r);
		else return binSearch(oneWayList, elem, l, middle-1);
	}

	@Override
	public long measureBubbleSort(int iterations) {
		// TODO Auto-generated method stub
		return 0;
	}
	
}
